Batch 2 - Class 300 - Moessner Miracle

• In how many ways can you distribute 10 identical balls into 4 distinct bags colored red, yellow, orange and green. You may place any number of balls in each bag, or leave a bag empty
• Answer: Consider the words formed by 10 B's and 3 P's (P being a partition where one bag ends and the next begins) - 13C3

• Let us start with a list of all odd numbers, and start to add them. So 1, 3, 5, 7, 9 .... add up to 1, 4, 9, 16, 25 ... respectively. What is the pattern?
• Can you prove that this will always be the case?

• Moessner started to explore this problem further. Let us start with list of all numbers 1, 2, 3, 4, 5, 6 ... Now we strike off each 2nd number, so all the even numbers will be gone. And now we add the remaining numbers. This gives us the sum of odd numbers, which we just saw add up to squares of numbers
• What happens if we strike off every 3rd number?
• Strike each 3rd number, and then add the remaining numbers. Now what?
• Now strike off each second number, and add again.
• What do we get? Cubes of numbers
• What seems to be happening? What should we try next?
• How about skipping every fourth or fifth integer? 
• Let kids try this out and come up with the patterns
• Moessner discovered that if we start off by striking out every nth integer, and continue this process, we land up with nth powers of integers
• How do we prove this? Any ideas? Remember that the proof of adding odd numbers was reliant on turning the next number into an L-shaped shell (called Gnomons)... So what could the cube proof look like?
• Can we find shells for 3-D cubes?

• What are the sizes of these shells and can we see them on our number grid?
• Lets take another view of the cube - the frontal view. Count the number of visible squares on this view

• So the number of visible square is nothing but the shells, and we can find them on our grid. Now one can understand why adding these shells leads to cubes!
• How do we knows that these numbers will always correspond to our number grid? Lets mark these numbers on second row of the grid differently on the cube.

• Now we can see how to construct the 3D shells using the numbers on our grid

• How do we extend the proof to higher dimensions, say n = 5. 

• If we take the circled numbers, these are just the number of squares in the 5-D cube shells. But we can't really visualize it. So is there another way to reason this?
• There is a graph theoretic proof of this. We will see this for n=5
• Look at the leftmost triangle of numbers in the grid - what are these? Tilt it a bit and you will see the Pascal's triangle, with an edge of 1st missing. So lets add that edge of 1s. Note that this set of 1s follows the scheme of addition

• We already know that the number on Pascal's triangle represents the number of paths from the tip to that number. 
• How is the second triangle built - it is still "Pascal"ish in the sense that any number is sum of two numbers above it (in this case the number above it and the number to the left of it). So we could again liken it to the number of paths - for example, assuming that there are 6 paths to the number 6 in second triangle grid, then the number of paths to the label 7 must be 7. 
• Also note that the left edge of second triangle is just sum of numbers above and to the left of it. So the overall paths total up as follows.

• What if we inverted all arrows, and then counted the number of paths from the last row to top left - the number of paths should be same as the forward paths. Lets count the number of paths. 
• The number of paths from the highlighted red cell to everything above it is 1. and hence when we go one left from each of those (the diagonal of the first triangular grid), there is one path each.
• Now, when we go to the second diagonal, we get all 2s, then all 4s and so on. So the left top number is 2^n. Note that this can also be derived because we know that sum of any row of the Pascal's triangle is 2^n

• Similarly, if we look at the next number on bottom row, now the outer diagonal of the second triangular grid will be 1s and so on. And the vertical edge of second triangular grid will be 1, 2, 4, 8, 16, 32. Notice that the power base goes up by 1 as you go from a diagonal of a triangular grid to the vertical edge. Then that base gets adopted on the next diagonal and the base increases by 1 as it translates to the vertical edge of that triangular grid, and so on. Why is this?

• See above how the diagonals total up to vertical edge. Now look at the coefficients on the top left square. What are those? (1,3,3,1) - these are binomial coefficients, also the same as numbers on Pascal's triangle. This just means that in this case the top left number is (3+1)^3 - the base has gone up by 1 in going from diagonal to vertical edge!

• Lets look at some other patterns on this
• Strike 1, then skip 1 and highlight, then skip 2 and highlight, and so on. Do Moessner sums with as many steps as you need, and see the pattern on the last numbers you get in each stack. What are these?
• What were the first set of numbers we struck out - these were sum of numbers (also triangular numbers). So the first strike offs were sum of numbers, and the final result was product of numbers. Sum turns into product

• Can you revisit the cubes grid - look at the first strike-offs and the final numbers. Here products are turning into cubes

• In general, if you start with a sequence of struck-off numbers, what sequence do you land up with? Try picking a sequence of non-negative integers and make up a struck-off sequence from it. 1a, 2a+1b, 3a+2b+c, 4a+3b+2c+d and so on. The sequence generated is 1^a, 2^ax1^b, 3^ax2^bx1^c and so on. Sum turns into products and products turn into powers. 
• We we make b,c,d,e all zero, we get our original sequence (and we can vary the length by varying a)
• Make 1=a=b=c=d... and we get the factorials

• (Geoffrey - 161 Modified) The sketch below shows the plan of industrial establishment with secret weapons. There are only three gates which are guarded. There is some information leakage, and they found this note supposedly written for the spy

• Answer: this is same as ways of arranging a number of 1's in a bit string. Since 210 appears as 5th number in 11th row, it must be at intersection of 7th and 5th Street (there is only one such combination above - if it was a larger grid, there would be two possibilities)